package LinkedLlist;

import java.util.List;

public class SingList {

    static class ListNode{
        public int vale;//节点的值
        public ListNode next;//下一个结点的地址

        public ListNode(int vale) {
            this.vale = vale;
        }

    }
    public ListNode head;//表示当前链表的头节点
    public void newlist() {
        ListNode head1 = new ListNode(10);
        ListNode head2 = new ListNode(20);
        ListNode head3 = new ListNode(30);
        ListNode head4 = new ListNode(40);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        this.head = head1;

    }
 //遍历打印
    public void display(){
        ListNode cur = head;
        while (cur != null ){
            System.out.println(cur.vale+"");
            cur =cur.next;
        }
        System.out.println();
    }
    //重载display方法
    public void display(ListNode x ){
        ListNode cur = x;
        while (cur != null ){
            System.out.println(cur.vale+"");
            cur =cur.next;
        }
        System.out.println();
    }
    //得到单链表的长度
    public int size(){
     int count = 0;
     ListNode cur = head;
     while (cur!=null){
         cur = cur.next;
         count++;
     }
     return count;
    }
//头插法
public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
}
//尾插法
public void addLast(int data){
    ListNode node = new ListNode(data);
    ListNode cur =head;
    if (cur == null){
        head = node;
        return;
    }
    while (cur.next!= null){
        cur =cur.next;
    }
    cur.next = node;
 }
//删除所有值为key的节点
public void removeAllKey(int key){
         if(head == null){
              return;
         }

        ListNode cur =head.next;
        ListNode prev = head;

        while (cur!=null){
            if(cur.vale==key){
                prev.next= cur.next;
                cur =cur.next;
            }else {
                prev =cur;
                cur =cur.next;
            }


        }
         if(head.vale == key){
             head = head.next;
         }


}
//返回链表中第k个节点
    public ListNode FindKthToTail (int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k-1 ; i++) {
            fast = fast.next;
            if(fast == null){
                return null;
            }
        }
        while (fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur!=null){
            if(cur.vale==key){
                return true;
            }
            cur =cur.next;
        }
         return false;
    }
//任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        if(index <0 ||index>size()){
           throw new run(index+"下标位置不合法");

        }
        //如何index为0则用头插方法
        if(index == 0){
            addFirst(data);
            return;
        }
        //如何index为 链表的长度则用尾插方法
        if (index ==size()){
            addLast(data);
            return;
        }
        ListNode cur = head;
        ListNode node = new ListNode(data);

        while (index-1 != 0) {

            cur = cur.next;
            index--;
        }
            node.next = cur.next;

            cur.next =node;


        }


 }

    /*public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        ListNode New = new ListNode(-1);
        ListNode head1 = pHead1;
        ListNode head2 = pHead2;

        ListNode head3 = New ;
        while (pHead1!=null&&pHead2!=null){
            if(head1.vale>head2.vale){
                head3.next =head1;
                head1 = head1.next;
            }else {
                head3.next =head2;
                head2 = head1.next;
            }
            head3 = head3.next;
        }
       if (pHead1!=null){
           head3.next =pHead1;

        }
       if(pHead2!=null){
           head3.next =pHead2;

        }
        // write code here
        return New;
    }
*/


